# -*- coding: utf-8 -*-

"""剑指 Offer II 045. 二叉树最底层最左边的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

示例 1:
输入: root = [2,1,3]
输出: 1

示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:
二叉树的节点个数的范围是 [1,10^4]
-231 <= Node.val <= 231 - 1 """

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """还是借鉴最右节点来分层，最右节点技能看下一层的最右节点，也能看下层的最左节点"""
    def findBottomLeftValue(self, root: TreeNode) -> int:
        leftmost, rightmost = root, root
        taskque = deque([])
        taskque.append(root)

        while True:
            try:
                node = taskque.popleft()
                if node.left:
                    taskque.append(node.left)
                if node.right:
                    taskque.append(node.right)
                
                if node is rightmost:
                    rightmost = taskque.pop()
                    taskque.append(rightmost)
                    leftmost = taskque.popleft()
                    taskque.appendleft(leftmost)
            except IndexError:
                break
        
        return leftmost.val
